﻿#include <iostream>
#include <vector>
#include <algorithm>
#include <stdexcept>

using namespace std;

template <class T>
class BinarySearchOptimizer {
private:
    int taskCount;           // 任务数量
    T maxAllowedResource;    // 最大可接受的资源使用
    T minResourceParameter;  // 资源参数
    vector<T> taskTimes;     // 每个任务的基本耗时
    vector<T> taskCosts;     // 每个任务的成本

    // 计算在给定最大耗时下所需的资源
    long long calculateRequiredResources(T maxTime) const {
        long long totalRequiredResources = 0;

        for (int i = 0; i < taskCount; i++) {
            if (taskTimes[i] > maxTime) {
                T excessTime = taskTimes[i] - maxTime;
                totalRequiredResources += static_cast<long long>(excessTime) * taskCosts[i];
                
                // 如果资源已超出限制，提前返回
                if (totalRequiredResources > maxAllowedResource) {
                    return totalRequiredResources;
                }
            }
        }
        return totalRequiredResources;
    }

public:
    BinarySearchOptimizer(int taskCount, T maxAllowedResource, T minResourceParameter, 
                          const vector<T>& times, const vector<T>& costs)
        : taskCount(taskCount), maxAllowedResource(maxAllowedResource), 
          minResourceParameter(minResourceParameter), taskTimes(times), taskCosts(costs) {}

    T findMinMaxTime();
};

template <class T>
T BinarySearchOptimizer<T>::findMinMaxTime() {
    T low = minResourceParameter;
    T high = *max_element(taskTimes.begin(), taskTimes.end());
    T result = high;

    while (low <= high) {
        T mid = low + (high - low) / 2;

        // 计算根据当前 mid 值所需的资源
        long long requiredResources = calculateRequiredResources(mid);

        if (requiredResources <= maxAllowedResource) {
            result = mid; // 记录满足条件的最小最大耗时
            high = mid - 1; // 尝试更小的最大耗时
        } else {
            low = mid + 1; // 尝试更大的最大耗时
        }
    }
    return result;
}

int main() {
    int n;
    long long m, k; // 支持较大的输入

    // 输入验证
    cout << "请输入任务数量 n, 最大可接受的耗时 m, 资源参数 k:" << endl;
    if (!(cin >> n >> m >> k) || n <= 0 || m < 0 || k < 0) {
        cerr << "输入无效，请确保输入为正整数且资源参数为非负。" << endl;
        return 1;
    }

    vector<long long> times(n), costs(n);
    for (int i = 0; i < n; i++) {
        cout << "请输入第 " << i + 1 << " 个任务的基本耗时和成本:" << endl;
        if (!(cin >> times[i] >> costs[i]) || times[i] < 0 || costs[i] < 0) {
            cerr << "输入无效，请确保任务耗时和成本为非负。" << endl;
            return 1;
        }
    }

    // 创建优化器实例并输出结果
    try {
        BinarySearchOptimizer<long long> optimizer(n, m, k, times, costs);
        cout << "最小的最大耗时为: " << optimizer.findMinMaxTime() << endl; 
    } catch (const exception& e) {
        cerr << "发生错误: " << e.what() << endl;
        return 1;
    }

    return 0;
}
